/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 *思路：前缀和
 */
class MaxSubArrayPreSum {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int[] preSum=new int[n+1];
        for(int i=1;i<=n;i++) {
            preSum[i]=preSum[i-1]+nums[i-1];
        }
        int res=Integer.MIN_VALUE;
        int minValue=Integer.MAX_VALUE;
        for(int i=0;i<n;i++) {
             // 维护 minVal 是 preSum[0..i] 的最小值
            minValue=Math.min(minValue,preSum[i]);
             // 以 nums[i] 结尾的最大子数组和就是 preSum[i+1] - min(preSum[0..i])
            res=Math.max(res,preSum[i+1]-minValue);
        }
        return res;
    }
}